Virtual machines are a useful way to encapsulate software environments. For example, a virtual machine can hold an operating system, applications, settings, and user data and settings. Using networks, software environments can be distributed by distributing virtual machines. Host devices can retrieve virtual machines from the network and run them to provide a user of the host device with a software environment. One of the challenges of distributing virtual machines is that virtual machines can take a long time to download from a network due to their large size.
An alternate approach is to start the virtual machine (VM) immediately and pull down the parts of the virtual machine as the virtual machine monitor (VMM) or guest operating system (OS) requests them. In many cases, this alternate approach, known as demand paging, allows the user to begin interacting with the virtual machine sooner than if they waited for the complete download. When the time to retrieve blocks from the server is higher than the time to retrieve blocks from the local disk, demand paging can lead to a virtual machine that is slower than a virtual machine that is fetched in its entirety. To hide this latency, demand paging can be supplemented by fetching blocks before they are requested by the virtual machine. This technique is called prefetching.
Prefetching requires a system to have excess capacity for the extra requests (e.g., pause times when the system can prefetch blocks). Effective prefetching also requires determining which blocks the virtual machine will request soon. One conventional method is to look at past request patterns and assume that future request patterns will be similar. For a new host device, however, there are no request patterns available.
Additionally, many virtual disk formats (e.g., Microsoft's VHD® and VMware's VMDK), allow blocks to be arranged in an order (e.g., an arbitrary order) within the actual file (or “disk file”), storing the virtual disk. This feature can be used to rearrange the blocks inside the disk file so that, for example, the blocks needed earlier by clients occur earlier in the file. By reading a sorted disk file sequentially, a client can fetch blocks according to a prefetch order. For digitally signed disks, reorganizing files creates a verification problem. For example, if a file is signed by one party and resorted by another, the integrity of the resorted file can become questionable, as an uncertainty can exist as to whether the signature of the file was maintained after the resorting.